Олимпиада по информатике, городской тур, Кемеровская область, 2005

Решение областной олимпиады школьников

Олимпиада по информатике

Городской тур, Кемеровская область, 2005 г.

Морозов Владимир,

учитель математики и информатики

МОУ «Школа 17»

г. Полысаево Кемеровской области

1. Противометеоритная защита. Для защиты космической станции от метеоритного дождя сделана специальная установка. Все метеориты засекаются радаром, после чего мощный лазер просто испаряет их. Внешнее сечение станции представляет собой квадрат. Лазерная установка находится в глубине станции на расстоянии Н от внешнего её сечения в центре сечения станции. Мощности лазера хватает на испарение метеоритов на дальности не более D. Метеориты летят перпендикулярно сечению станции. Дальности стрельбы достаточно для того, чтобы сбивать метеориты до того, как они долетят до плоскости внешнего сечения станции. Более того, установка в порядке благотворительности сбивает даже те метеориты, которые не попадают в станцию. Требуется определить, сколько метеоритов из тех, что видно на радаре, будет сбито.

Входной файл input.txt:

Первая строка содержит Н (1.00<=H<=100.00).

Следующие 4 строки содержат пары вещественных чисел – координаты вершин космической станции.

На следующей строке находится D (Н<D<1000.00).

После этого строка, содержащая k (1<=k<=100) – количество метеоритов.

Следующие k строк содержат пары вещественных чисел – координаты метеоритов в плоскости сечения станции. Все координаты по модулю не превосходят 1000.

Пример входного файла:

10.00

1.00 0.00

0.00 1.00

-1.00 0.00

0.00 -1.00

50.00

0.00 0.00

1.00 1.00

2.00 2.00

3.00 3.00

4.00 4.00

Пример выходного файла output.txt:

Решение. В этой задаче достаточно много математических выкладок. Сначала найдём координаты пушки – точки Р(px,py,pz). Систему координат расположим так, чтобы ось OZ была направлена через пушку навстречу метеоритам, квадрат располагался в плоскости XOY, а начало координат – в плоскости квадрата. Посмотрите на рисунок 1. Ясно, что лазер в состоянии испарить метеорит, если он попадёт в сферу радиуса d с центром в пушке P, а также если этот метеорит будет засечён радаром, то есть, если он попадёт в бесконечную пирамиду (см. рис. 1). Поэтому найдём координаты точки Q на сфере, куда попадёт метеорит. При этом возможна ситуация, когда метеорит вообще пройдёт мимо сферы, то есть заведомо вне пределов досягаемости пушки.

Пусть координаты данного метеорита (x,y). Координату z точки Q на сфере находим так:

z:=pz+sqrt(d*d-(x-px)*(x-px)-(y-py)*(y-py));

Находим координаты вектора PQ.

p:=x-px;

q:=y-py;

r:=z-pz;

Получаем уравнение прямой PQ (точка с координатами (xx,yy) – точка на прямой PQ):

(xx–px)/p = (yy–py)/q=(0–pz)/r

Отсюда находим координаты пересечения прямой PQ и плоскости станции. Таким образом мы узнаем, попадает ли метеорит одновременно и в сферу, и в бесконечную пирамиду.

xx:=px-p*pz/r;

yy:=py-q*pz/r;

Итак, точка R(xx,yy) в плоскости квадрата найдена. Осталось определить, попала ли точка R в квадрат. Посмотрите на рисунок 2. Очевидно, что точка R попадает в квадрат (а может и в его границу), если и только если сумма площадей четырёх треугольников S1+S2+S3+S4 равна площади квадрата. Для этого нам потребуется функция, которая по трём вершинам треугольника будет находить его площадь. Это удобно осуществить по формуле Герона.

function striangle(aax,aay,bbx,bby,ccx,ccy:real):real;

{Функция получает на вход координаты вершин треугольника и вычисляет

площадь треугольника по формуле Герона}

var a,b,c,p:real;

begin

c:=sqrt(sqr(aax-bbx)+sqr(aay-bby));

b:=sqrt(sqr(aax-ccx)+sqr(aay-ccy));

a:=sqrt(sqr(ccx-bbx)+sqr(ccy-bby));

p:=(a+b+c)/2;

striangle:=sqrt(p*(p-a)*(p-b)*(p-c));

end;

Функция, определяющая, можно ли сбить данный метеорит полностью приводится здесь:

function ff(x,y:real):boolean;

{Функция проверяет, попадает ли метеорит в зону действия радара

и находится в пределах досягаемости лазера}

var ss,sss,xx,yy,px,py,pz,z,p,q,r,s1,s2,s3,s4,qq:real;

begin

{Координаты лазерной пушки:}

px:=(ax+bx+cx+dx)/4;

py:=(ay+by+cy+dy)/4;

pz:=-h;

{Отыскиваем координату z так, чтобы точка с координатами

(x,y,z) была на сфере радиуса d с центром лазерной пушке

По сути, эта точка - ортогональная проекция метеорита,

а поэтому метеорит рано или поздно в этой точке окажется}

qq:=d*d-(x-px)*(x-px)-(y-py)*(y-py);

if qq<0

then

ff:=false {Метеорит не пересекает сферу и проходит слишком далеко}

else

begin

z:=pz+sqrt(qq);

p:=x-px;

q:=y-py;

r:=z-pz;

{(p,q,r) - координаты вектора с началом в пушке и концом в точке

(x,y,z) на сфере}

{Находим координаты пересечения прямой (пушка-точка на сфере)

с плоскостью z=0, с плоскостью станции:}

xx:=px-p*pz/r;

yy:=py-q*pz/r;

{проверяем, попала ли точка (xx,yy) внутрь квадрата

иными словами, достигает ли пушка мееторита}

s1:=striangle(ax,ay,bx,by,xx,yy);

s2:=striangle(bx,by,cx,cy,xx,yy);

s3:=striangle(cx,cy,dx,dy,xx,yy);

s4:=striangle(dx,dy,ax,ay,xx,yy);

ss:=s1+s2+s3+s4;

sss:=sqr(ax-ay)+sqr(bx-by);

ff:=(abs(ss-sss)<1e-7);

end

end;

Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (2K).

2. Геном марсианина. Сотрудники лаборатории внеземных цивилизаций обнаружили в пробах марсианского грунта фрагменты органических молекул, которые могли бы переносить генную информацию. Зашифрованные фрагменты молекул образуют отдельные слова. Известно, фрагменты молекул могут соединяться, если на конце предыдущей и в начале последующей молекулы стоят одинаковые символы. Переворачивать фрагменты не надо. Каждый фрагмент в виде целого слова используется только один раз.

Входной файл input.txt

Первая строка содержит N – количество фрагментов, не более 100.

Последующие N строк – зашифрованные в виде отдельных слов фрагменты молекул (не более чем по 100 символов).

Выходной файл output.txt – максимальная длина полной молекулы.

Пример входного файла:

12345

543

54321

Выходной файл output:

Решение. Для решения задачи нам потребуются некоторые типы:

type string100=string[100];

sto=1..100;

Основная ошибка, которую учащиеся могут допускать при решении этой задачи (во всяком случае допускали у нас в городе Полысаево) – это пытаться сразу склеивать первые подходящие строки, пусть даже они самые длинные. Но ясно, при такой склейке мы можем просмотреть много коротких склеек, которые в сумме дадут большую общую длину. И тогда программа будет работать лишь для некоторых частных случаев, но не в общем виде. Причём могут склеиваться самые разные строки в самом непредсказуемом порядке, и очень может быть, что будут склеиваться не только какие-то две строки, но гораздо больше. По существу, нужно провести аккуратный перебор всех случаев.

Идея решения этой задачи такова.

Заведём вспомогательную прямоугольную таблицу Х целых чисел. Будем туда записывать номера строк, которые можно склеить. Например, пусть мы получили во входном файле следующие строки:

12345

543

54321

1-ю строку можно склеить со второй. Записываем в 1-ю строку таблицы Х номера слов по порядку, которые можно склеить: 1, 2.

1-ю строку можно склеить с третьей. Записываем в следующую строку таблицы Х номера слов по порядку, которые можно склеить: 1, 3. Больше первая строка ни с какой не склеивается.

Вторая строка тоже ни с какой не склеивается.

3-ю строку можно склеить с первой. Записываем в следующую строку таблицы Х номера слов по порядку, которые можно склеить: 3, 1.

3-ю строку можно склеить с четвёртой. Записываем в следующую строку таблицы Х номера слов по порядку, которые можно склеить: 3, 4.

Получили таблицу Х:

1 2 0 0 0 ...

1 3 0 0 0 ...

3 1 0 0 0 ...

3 4 0 0 0 ...

Снова просмотрим таблицу Х. Первая строка оканчивается на 2, и больше с двойки ничто не начинается, значит, нет ни одной молекулы, начинающейся со слова 2, и эта молекула длиннее сделана быть не может.

Вторая строка оканчивается на 3, а третья строка с тройки начинается. Но склеен они быть не могут, поскольку в 3-й строке используется тот же номер, что и во второй, а по условию задачи нельзя использовать одну молекулу несколько раз.

Но 2-я и 4-я строки прекрасно склеиваются. Получаем цепочку 1 3 4, значит, можно по порядку склеить 1-ю, 3-ю и 4-ю молекулы.

3-я строка склеивается с 1-й, получаем цепочку 3 1 2. Значит, можно по порядку склеить 3-ю, 1-ю и 2-ю молекулы. Такая склейка, кстати, и даёт самую длинную молекулу.

Получили таблицу Х:

1 2 0 0 0 ...

1 3 4 0 0 ...

3 1 2 0 0 ...

3 4 0 0 0 ...

Будем просматривать так таблицу в цикле Х до тех пор, пока не будет сделано ни одного нового изменения в этой таблице. Ясно, что процесс рано или поздно закончится.

После этого останется только просмотреть таблицу Х, каждую строку, для каждой строки определить длину соответствующей склеенной в этом порядке молекулы (это сумма длин строк с данными номерами в этой строке таблицы Х), и среди всех этих длин найти максимальную.

Наиболее интересный сегмент описываемого кода приводится ниже.

...

k:=1;

for i:=1 to n do

for j:=1 to n do

if i<>j {Сравниваем разные строки i и j}

then

begin

{try to join i and j string}

{сравниваем последний символ i строки и первый символ j строки}

if h[i][length(h[i])]=h[j][1]

then

begin

{one can join strings i and j}

{Строки можно склеить}

x[k,1]:=i;

x[k,2]:=j;

{Во вспомогательную таблицу в строку с номером к

записали номера строк, которые можно склеить в данном порядке}

inc(k);

end

end;

k:=k-1;

{k - количество строк вспомогательной таблицы х

- количество возможных пар потенциально склеиваемых строк}

{here we shall begin a loop}

repeat

LL:=true; {Флаг, признак того, что вспомогательная матрица х готова}

{Обрабатываем вспомогательную матрицу х

проверяем, можно ли склеивать дальше

склеиваем только те строки, которые ранее не склеивались

для этого используем множества}

for i:=1 to k do {просматриваем каждую строку вспомогательной матрицы}

begin

j:=1;

while x[i,j]<>0 do inc(j);

j:=j-1; {Определили длину i-й строки вспомогательной матрицы

нули не считаем}

for ii:=1 to k do

if i<>ii {Сравниваем различные строки вспомогательной матрицы i и ii}

then

begin

j1:=1;

while x[ii,j1]<>0 do inc(j1); j1:=j1-1;

{Определили длину строки ii}

if x[i,j]=x[ii,1] {Проверяем их на возможность склейки}

then

begin

{Проверяем, строки i и ii, если они содержат

одинаковые элементы, то склеивать их нельзя}

a:=[]; L:=false; {Флаг, что строки можно склеивать}

for jj:=1 to j do

a:=a+[x[i,jj]];

{а - множество, состоящее из элементов i-строки матрицы х}

writeln;

for jj:=2 to j1 do

L:=L or (x[ii,jj] in a);

if not(L)

then

begin

{Строки матрицы х состоят из разных номеров,

и текстовые строки можно склеивать дальше}

for i1:=1 to j1-1 do

begin

{К концу строки i приписываем строку ii

и в этом случае опускаем флаг,

и в следующем проходе цикла снова

будем искать, можно ли продолжить склейку

строк}

x[i,j+i1]:=x[ii,i1+1];

LL:=false

end

end;

until LL;

{В итоге в каждой строке матрицы Х записаны номера строк,

которые можно склеить. Осталось только обработать каждую

строку матрицы Х, найти суммарную длину, и найти из этих

суммарных длинн максимальную}

smax:=0;

for i:=1 to k do

begin

j:=1;

while x[i,j]<>0 do inc(j);

j:=j-1; {Снова ищем длину i-й строки}

sss:=0;

for ii:=1 to j do

sss:=sss+length(h[x[i,ii]]);

if sss>smax

then

smax:=sss;

end;

writeln(smax);

...

Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (2K).

3. Шифр Цезаря. Известно, что символы в электронных документах кодируются разными числами при помощи кодировочных таблиц. Это позволяет кодировать сообщение, делая сдвиг по кодировочной таблице для каждого символа всего текста. Написать программу, реализующую сдвиг (ключ задаётся) только для больших латинских букв.

Входной файл input.txt

В первой строке размещается зашифрованный текст.

Во второй – ключ.

Выходной файл output.txt содержит расшифрованный текст.

Пример входного файла:

ABZ

Выходной файл output:

CDB

Решение. Это самая простая задача из предложенных на олимпиаде. Приведённый ниже код осуществляет требуемый сдвиг. Программа понимает и отрицательные сдвиги.

...

for i:=i to n do

begin

c:=h[i];

k:=ord(c);

inc(k,dd);{Осуществляем сдвиг}

if k>ord('Z')

then

dec(k,26);

if k<ord('A')

then

inc(k,26); {Поправка, если вышли за рамки алфавита}

c:=char(k); {Изменённый символ}

hh[i]:=c

end;

writeln(hh); {Готовая строка}

...

Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (1K).

Вопросы и замечания можно отправить автору статьи Морозову В. В.